#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int n = heights.size();
        int m = heights[0].size();
        vector<vector<bool>> pacific(heights.size(),
            vector<bool>(heights[0].size(), false));
        vector<vector<bool>> atlantic(heights.size(),
            vector<bool>(heights[0].size(), false));
        for (int i = 0; i < m; i++) {
            dfs(heights, pacific, 0, i);
        }
        for (int i = 0; i < n; i++) {
            dfs(heights, pacific, i, 0);
        }
        for (int i = 0; i < m; i++) {
            dfs(heights, atlantic, n - 1, i);
        }
        for (int i = 0; i < n; i++) {
            dfs(heights, atlantic, i, m - 1);
        }
        vector<vector<int>> result;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (atlantic[i][j] && pacific[i][j]) {
                    result.push_back({ i, j });
                }
            }
        }
        return result;
    }

private:
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& ocean, int i,
        int j) {
        int n = heights.size();
        int m = heights[0].size();
        if (ocean[i][j])
            return;
        ocean[i][j] = true;
        vector<vector<int>> directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        for (auto& dir : directions) {
            int ni = i + dir[0];
            int nj = j + dir[1];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m &&
                heights[ni][nj] >= heights[i][j]) {
                dfs(heights, ocean, ni, nj);
            }
        }
    }
};